# -*- coding: utf-8 -*-


"""

    https://stackoverflow.com/questions/59195915/generate-the-initial-game-board-of-a-candy-crush-like-game
"""

from pprint import pprint
from random import shuffle
import time


class NumCounter:
    def __init__(self):
        self.remain_counter = [9, 9, 9, 9]
        self.kinds = 4

    def try_get(self, num):
        idx = num - 1
        if self.remain_counter[idx] > 0:
            self.remain_counter[idx] -= 1
            return num

        return None

    def put(self, num):
        idx = num - 1
        self.remain_counter[idx] += 1


class Solution:
    def __init__(self):
        self.num_counter = NumCounter()

        self.width = 6
        self.board = self.init_board()

        self.base_order = [1, 2, 3, 4]


    def init_board(self):
        one_row = [0] * self.width
        board = [ list(one_row) for i in range(self.width)]
        return board

    def make_board(self):
        for next_try_num in self.number_resource():
            if self.recursive_try(0, 0, self.num_counter.try_get(next_try_num)):
                return self.board
            else:
                self.num_counter.put(num)
        else:
            return None

    def recursive_try(self, row, col, try_num):
        print("try (%s %s) %s" % (row, col, try_num))
        self.board[row][col] = try_num
        fine = self.is_valid(row, col, try_num)

        if not fine:
            # self.num_counter.put(try_num)
            # 告知上一层递归, 这个try_num 不可行, 再换一个try_num吧!
            return False


        # ------------ 下面都是fine之后的操作 ----------------
        if self.is_end(row, col):
            # 已经到最后一个slot, 不用再递归了. 告知上一层递归, game over, 已经有解了
            return True

        next_row, next_col = self.next_position(row, col)

        for next_try_num in self.number_resource():
            if self.num_counter.try_get(next_try_num) is None:
                continue

            if self.recursive_try(next_row, next_col, next_try_num):
                return True
            else:
                # 当前这个数在这个位置不成, 换下个数试试!
                self.num_counter.put(next_try_num)


        # 所有的情况都试完了, 告诉上层递归: 目前状态下, 所有试法都不行. 让上层递归再换换方案.
        return False

    def is_end(self, row, col):
        return row == 5 and col == 5

    def next_position(self, row, col):
        if col == 5:
            return row + 1, 0

        return row, col + 1

    def is_valid(self, row, col, try_num):
        ret = True

        # 检查第row行
        begin_col = max(0, col-2)
        if col - begin_col == 2:
            if self.board[row][col] == self.board[row][col-1] == self.board[row][col-2]:
                return False

        # 检查第col列
        begin_row = max(0, row-2)
        if row - begin_row == 2:
            if self.board[row][col] == self.board[row-1][col] == self.board[row-2][col]:
                return False

        #  相邻斜对角不能相同, is_valid()更严格, 返回False的可能性更大.
        #  则调用 is_valid()处需要尝试更多的循环
        if row > 0:
            if col > 0 and try_num == self.board[row-1][col-1]:
                return False

            if col < 5 and try_num == self.board[row-1][col+1]:
                return False


        return True


    def number_resource(self):
        # return self.base_order
        # return [4, 3, 2, 1]       # 由此得出的结果是[1, 2, 3, 4] 的同构体

        shuffle(self.base_order)
        return self.base_order


if __name__ == '__main__':
    now = time.time()
    s = Solution()
    pprint(s.make_board())
    print(time.time() - now)
    # pprint(s.board)
    pprint(s.num_counter.remain_counter)
